package demo2;

import java.util.*;

class Node {
    public int val;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _next) {
        val = _val;
        next = _next;
    }
};

class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }

public class Solution {

//    //1.剑指 Offer 16. 数值的整数次方(数学-超时)
//    public double myPow(double x, int n) {
//        int tmpN = n < 0 ? -n : n;
//        double tmpX = x;
//        for(int i = 0; i < tmpN; i++) {
//            tmpX *= x;
//        }
//        return n < 0 ? 1L / tmpX : tmpX;
//    }

    //1.剑指 Offer 16. 数值的整数次方(快速幂)
    public double myPow(double x, int n) {
        if(n == 0) {
            return 1;
        }
        double ret = 1.0;
        long m = n;
        if(m < 0) {
            m = -m;
            x = 1 / x;
        }
        while(m > 0) {
            if((m & 1) == 1) {
                ret *= x;
            }
            x *= x;
            m >>= 1;
        }
        return ret;
    }

    //2.剑指 Offer 62. 圆圈中最后剩下的数字(神奇的ArrayList)
    public int lastRemaining(int n, int m) {
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            list.add(i);
        }
        int index = (m - 1) % list.size();
        while(list.size() != 1) {
            list.remove(index);
            index = (index + m - 1) % list.size();
        }
        return list.get(0);
    }

    //3.剑指 Offer 56 - II. 数组中数字出现的次数 II(数电-这样子好吗？)
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        for(int key : map.keySet()) {
            if (map.get(key) == 1) {
                return key;
            }
        }
        return -1;
    }

    //4.剑指 Offer 66. 构建乘积数组(数学)
    public int[] constructArr(int[] a) {
        int len = a.length;
        int[] b = new int[len];
        int ans = 1;
        for(int i = 0; i < len; i++) {
            b[i] = ans;
            ans *= a[i];
        }
        ans = 1;
        for(int i = len - 1; i >= 0; i--) {
            b[i] *= ans;
            ans *= a[i];
        }
        return b;
    }

    //5.剑指 Offer 65. 不用加减乘除做加法(数学)
    public int add(int a, int b) {
        int yi = 0;
        int yu = 0;
        while(true) {
            yi = a ^ b;
            yu = (a & b) << 1;
            if((yi & yu) == 0) {
                break;
            }
            a = yi;
            b = yu;
        }
        return yi | yu;
    }

    //6.对链表进行插入排序
    public ListNode insertionSortList(ListNode head) {
        if(head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode cur = head;
        while(cur != null && cur.next != null) {
            if(cur.val <= cur.next.val) {
                cur = cur.next;
                continue;
            }
            //此时cur.val > cur.next.val
            ListNode insert = cur.next;
            cur.next = cur.next.next;
            ListNode prev = dummy;

            while(prev.next.val < insert.val) {
                prev = prev.next;
            }
            insert.next = prev.next;
            prev.next = insert;
        }
        return dummy.next;
    }

    //7.剑指 Offer II 077. 链表排序(归并-plus优化)
    public ListNode sortList(ListNode head) {
        return head == null ? null : mergeSort(head);
    }

    private ListNode mergeSort(ListNode left) {
        if(left.next == null) {
            return left;
        }
        ListNode fast = left, slow = left;
        ListNode mid = null;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            mid = slow;
            slow = slow.next;
        }
        mid.next = null;
        ListNode l1 = mergeSort(left);
        ListNode l2 = mergeSort(slow);
        return merge(l1, l2);
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        if(l1 != null) {
            cur.next = l1;
        }
        if(l2 != null) {
            cur.next = l2;
        }
        return dummy.next;
    }

    //8.剑指 Offer II 029. 排序的循环链表(恶心的边界条件)
    public Node insert(Node head, int insertVal) {
        //链表为空
        if(head == null) {
            head = new Node(insertVal);
            head.next = head;
            return head;
        }
        //只有一个结点
        if(head.next == head) {
            Node node = new Node(insertVal);
            if(head.val < node.val) {
                head.next = node;
                node.next = head;
            } else {
                node.next = head;
                head.next = node;
            }
            return head;
        }
        //不止一个结点
        Node node = new Node(insertVal);
        Node cur = head;
        //1)先找到下一个结点是最小值的结点
        while(cur.val <= cur.next.val) {
            cur = cur.next;
            if(cur == head) {//值都一样，随便插一个位置
                node.next = cur.next;
                cur.next = node;
                return head;
            }
        }
        Node max = cur;//记录当前最大的结点
        //2)找一个合适的插入位置
        while(cur.next.val < insertVal) {
            cur = cur.next;
            if(cur == max) { //防止insertVal比所有值都大
                break;
            }
        }
        node.next = cur.next;
        cur.next = node;
        return head;
    }

    //9.山脉数组的峰顶索引(二分法)
    public int peakIndexInMountainArray(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(arr[mid] < arr[mid + 1]) {
                left = mid + 1;
            } else if(arr[mid] < arr[mid - 1]) {
                right = mid - 1;
            } else {
                return arr[mid];
            }
        }
        return -1;
    }

    //10.剑指 Offer II 002. 二进制加法(数学)
    public String addBinary(String a, String b) {
        StringBuilder num = new StringBuilder();
        int len1 = a.length();
        int len2 = b.length();
        int ans = 0;//进位
        for(int i = len1 - 1, j = len2 - 1; i >= 0 || j >= 0; i--,j--) {
            int num1 = i < 0 ? 0 : a.charAt(i) - '0';
            int num2 = j < 0 ? 0 : b.charAt(j) - '0';
            int sum = (num1 + num2 + ans) % 2;
            ans = (num1 + num2 + ans) / 2;
            num.append(sum);
        }
        if(ans != 0) {
            num.append(1);
        }
        return num.reverse().toString();
    }

}

class Main {
    public static void main(String[] args) {
        int[] arr = {4, 2, 1, 3};
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        for(int i = 0; i < arr.length; i++) {
            cur.next = new ListNode(arr[i]);
            cur = cur.next;
        }
        Solution solution = new Solution();
        solution.sortList(dummy.next);
    }
}

//5.剑指 Offer 41. 数据流中的中位数(排序)
class MedianFinder {

    private List<Integer> list = null;

    /** initialize your data structure here. */
    public MedianFinder() {
        this.list = new ArrayList<>();
    }

    public void addNum(int num) {
        list.add(num);
        //对这个元素进行插入排序
        int j = list.size() - 2;
        for(; j >= 0; j--) {
            if(list.get(j) > num) {
                list.set(j + 1, list.get(j));
            } else {
                break;
            }
        }
        list.set(j + 1, num);
    }

    public double findMedian() {
        if(list.size() % 2 == 0) { //偶数
            int index = list.size() / 2 - 1;
            double ret = (list.get(index) + list.get(index + 1)) / 2.0;
            return ret;
        } else {
            int index = (list.size() - 1) / 2;
            return list.get(index);
        }
    }

}

